package com.example.demo.leetcode.level2;

public class 排序链表 {


    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    // 找到链表中心点，拆分，排序后合并
//    public ListNode sortList(ListNode head) {
//
//        ListNode middle = findMiddle(head);
//        ListNode fisrt = head;
//        ListNode second = middle.next;
//        middle.next = null;
//
//        ListNode left = sortList(fisrt);
//        ListNode right = sortList(second);
//        ListNode merge = merge(left, right);
//        return merge;
//    }

//    public ListNode merge(ListNode left, ListNode right){
//
//    }


    public ListNode findMiddle(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while(slow != null && fast != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


}
